package jianzhi

func copyRandomList(head *Node) *Node {

	if head == nil {
		return nil
	}

	copyMap := make(map[*Node]*Node)
	for temp := head; temp != nil; temp = temp.Next {
		newNode := &Node{
			Val: temp.Val,
		}
		copyMap[temp] = newNode
	}

	newHead := copyMap[head]
	cur := newHead
	for temp := head; temp != nil; temp, cur = temp.Next, cur.Next {
		cur.Next = copyMap[temp.Next]
		cur.Random = copyMap[temp.Random]
	}

	return newHead

}
